%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Program Execution Prediction and Identification}~\label{chap:prediction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The Cardinal Execution Map has many inherent characteristics which make it
possible to both predict future program events and to identify single input
behavior from a group of inputs to the same program. This chapter explores
program prediction and identification using CEMs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Program Prediction Using a Markov Model}~\label{sec:pred_markov}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One advantage to using a graph as the representation is the many
mathematical models that can be applied to a graph. One such model is
a Markov model. This section describes the use of a Markov model to
perform program prediction using the CEM.

Figure~\ref{fig:markov_cem} shows an example CEM labeled in two
different ways.  Figure~\ref{fig:markov_cem}(a) shows a CEM with the
edges labeled as the number of transitions whereas
Figure~\ref{fig:markov_cem}(b) shows the same CEM but the edges are
labeled with probabilities. The probabilities are found by dividing
the edge's outgoing transitions by the total number of outgoing
transitions for the node.

\begin{figure}[t!]
    \centering
    \begin{tabular}{cc}
        \centering
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.3]{fig/markov}
        \hspace{2pt}
        \end{minipage}
        &
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.3]{fig/markov_prob}
        \end{minipage}

    \\ (a) \textit{CEM.} & (b) \textit{CEM labeled with probabilities.}
    \end{tabular}
    \caption{Example CEM in (a) with the probabilities labeled in (b).}
    \label{fig:markov_cem}
\end{figure}

The graph containing the probabilities can be converted into matrix
form.  Figure~\ref{fig:markov_prob_mat} shows the connectivity matrix
for this graph with the entries being the probabilities.
The columns represent the 'from' node while the rows
represent the 'to' node.  For example, Node 1 transitioning to Node 2
happens with probability 0.333 while Node 3 transitioning to Node 0
happens with probability 0.000.

\begin{figure}[t!]
\centering
\[
\begin{array}{c|cccc}
      & 0     & 1     & 2     & 3     \\
\hline
    0 & 0.968 & 0.000 & 0.000 & 0.000 \\
    1 & 0.032 & 0.167 & 0.000 & 0.167 \\
    2 & 0.000 & 0.333 & 0.889 & 0.833 \\
    3 & 0.000 & 0.500 & 0.111 & 0.000 \\
\end{array}
\]
\caption{Probability matrix for the example CEM shown in
Figure~\ref{fig:markov_cem}.}
\label{fig:markov_prob_mat}
\end{figure}

This matrix can be used perform predictions into the future execution
of the program. For example, if the program is found to be in Node 1,
a calculation can be done to find the most likely next node. This
calculation is found in Figure~\ref{fig:markov_pred_one_stage}. The
probability matrix is multiplied by a vector containing a 1 in the
position of the current node and the rest 0s. The resulting vector
shows the most likely next node is Node 3.

\begin{figure}[b!]
\centering
\[
\begin{bmatrix}
    0.968 & 0.000 & 0.000 & 0.000 \\
    0.032 & 0.167 & 0.000 & 0.167 \\
    0.000 & 0.333 & 0.889 & 0.833 \\
    0.000 & 0.500 & 0.111 & 0.000 \\
\end{bmatrix}
\begin{bmatrix}
    0 \\
    1 \\
    0 \\
    0 \\
\end{bmatrix}
=
\begin{bmatrix}
    0.000 \\
    0.167 \\
    0.333 \\
    0.500 \\
\end{bmatrix}
\]
\caption{Calculation for prediction one stage into the future.}
\label{fig:markov_pred_one_stage}
\end{figure}

To predict further into to future, all that has to be done is to
multiply the probability matrix by itself for each step into the future.
For example, if a
prediction is to be made 2 stages into the future, the probability
matrix is multiplied by itself and then the vector. The 2 stage
prediction calculation is shown in
Figure~\ref{fig:markov_pred_two_stage}. The resulting vector indicates that the
program will most likely be executing in Node 2 in two stages.

\begin{figure}[t!]
\centering
\[
\begin{bmatrix}
    0.968 & 0.000 & 0.000 & 0.000 \\
    0.032 & 0.167 & 0.000 & 0.167 \\
    0.000 & 0.333 & 0.889 & 0.833 \\
    0.000 & 0.500 & 0.111 & 0.000 \\
\end{bmatrix}
\begin{bmatrix}
    0.968 & 0.000 & 0.000 & 0.000 \\
    0.032 & 0.167 & 0.000 & 0.167 \\
    0.000 & 0.333 & 0.889 & 0.833 \\
    0.000 & 0.500 & 0.111 & 0.000 \\
\end{bmatrix}
\begin{bmatrix}
    0 \\
    1 \\
    0 \\
    0 \\
\end{bmatrix}
=
\begin{bmatrix}
    0.000 \\
    0.111 \\
    0.768 \\
    0.120 \\
\end{bmatrix}
\]
\caption{Calculation for prediction two stages into the future.}
\label{fig:markov_pred_two_stage}
\end{figure}

This process can be generalized for a prediction N stages in to the
future.  Given a probability matrix \(P\) and a vector \(V_{n}\) a
probability vector \(V_{p}\) can be found which shows the
probabilities of reaching all nodes in the
graph. Figure~\ref{fig:markov_pred_formula} shows the general formula.

\begin{figure}[h!]
\centering
\begin{equation*}
    V_{p} = P^{N}V_{n}
\end{equation*}
\caption{Formula for predicting N stages into the future for a CEM with
probability matrix P.}
\label{fig:markov_pred_formula}
\end{figure}
%Figure~\ref{fig:exemap_177_mesa_single_input_prob} shows the same graph that is
%shown in Figure~\ref{fig:exemp_177_mesa_single_input} but
%with the edges labeled as probabilites instead of raw transistion counts.

%\begin{figure}[ht!]
%    \begin{tabular}{c}
%        \begin{minipage}{\textwidth}
%            \centering
%            \includegraphics[scale=0.35]{fig/177_mesa_ref_0_prob} \\
%        \end{minipage} \\
%    \end{tabular}
%    \caption{CEM for 177.mesa labeled with probabilities instead of transistion
%counts.}
%\label{fig:exemap_177_mesa_single_input_prob}
%\end{figure}
%
%\begin{figure}[h]
%\centering
%\[
%%\left[
%\begin{array}{c|cccccc}
%      & 0     & 1     & 2     & 3     & 4     & 5     \\
%\hline
%    0 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 \\
%    1 & 0.000 & 0.995 & 0.005 & 0.000 & 0.000 & 0.000 \\
%    2 & 0.000 & 0.000 & 0.853 & 0.116 & 0.031 & 0.000 \\
%    3 & 0.000 & 0.000 & 0.003 & 0.996 & 0.001 & 0.000 \\
%    4 & 0.000 & 0.000 & 0.625 & 0.375 & 0.000 & 0.000 \\
%    5 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 \\
%\end{array}
%%\right]
%\]
%\caption{Probablilty matrix for 177.mesa.}
%\end{figure}
%
%\[
%\begin{bmatrix}
%    0 & 1 & 0 & 0 & 0 & 0 \\
%\end{bmatrix}
%\begin{bmatrix}
%    0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 \\
%    0.000 & 0.995 & 0.005 & 0.000 & 0.000 & 0.000 \\
%    0.000 & 0.000 & 0.853 & 0.116 & 0.031 & 0.000 \\
%    0.000 & 0.000 & 0.003 & 0.996 & 0.001 & 0.000 \\
%    0.000 & 0.000 & 0.625 & 0.375 & 0.000 & 0.000 \\
%    0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 \\
%\end{bmatrix}
%=
%\begin{bmatrix}
%    0.000 & 0.995 & 0.005 & 0.000 & 0.000 & 0.000 \\
%\end{bmatrix}
%%\begin{bmatrix}
%%    0 \\
%%    1 \\
%%    0 \\
%%    0 \\
%%    0 \\
%%    0 \\
%%\end{bmatrix}
%\]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Results of Single Program Prediction}~\label{sec:pred_single}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Using a Markov Model, the graphs for a set of the
SPEC2000 benchmarks are analyzed. The number of
predictions from the current position are varied from 1 step to 10 steps.
The accuracy of these predictions are made when the predicted state is
matched with the exact future state occurring in the timeline.
The prediction
results of Figure~\ref{fig:pred_single_overall} demonstrate that for
most of the programs the prediction accuracy remains nearly the
same from 1 step out to 10 steps. Looking at the average accuracy, 15 out of the
20 programs show an average accuracy of at least 65\%.

\begin{figure}[t!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=1.0]{fig/spec2000_prediction_ave_bars.pdf} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Prediction accuracy for 20 of the SPEC2000 benchmarks for a range
of 1 to 10 steps into the future showing the minimum, average and maximum accuracy.}
\label{fig:pred_single_overall}
\end{figure}

Another way to examine at the prediction results is to evaluate the
prediction accuracy over time. Figure~\ref{fig:pred_single_time_crop} shows the percent
difference from 1 step to 5 step, for the SPEC2000 program
183.equake, 187.facerec, and 254.gap.  The comparison between the
prediction accuracy for 1 to 5 steps illustrates the ability of the
CEM to be used to predict near term (1 step) compared to
moderate distance (5 steps).  The timelines show that execution graphs
can be used to accurately predict the code execution of a program
in the near and far ahead future.  In addition, using the execution
graphs, there appear to be very stable periods of time that their use
can be relied upon to deliver accurate expectations of the state of
program execution.  Moreover, the times when prediction
accuracy differences between 1 step to 5 steps are significant appear
to be predictable or phase-based.

%\begin{figure}[ht!]
%    \begin{tabular}{c}
%        \begin{minipage}{\textwidth}
%            \centering
%            \includegraphics[scale=0.35]{fig/164_gzip_ref_0_timeline_crop.pdf} \\
%        \end{minipage} \\
%    \end{tabular}
%    \caption{Prediction over time.}
%\label{fig:pred_single_time_crop}
%\end{figure}

\begin{figure}[t!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=1.0]{fig/prediction_diff.pdf} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Difference in prediction accuracy from 1 step to 5 steps for
183.equake, 187.facerec and 254.gap.}
\label{fig:pred_single_time_crop}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Program Input Identification}~\label{sec:pred_input_id}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

As mentioned in Chapter~\ref{chap:methodology} a CEM can be looked at
in terms of its nodes or the paths found in its timeline. With the
Composite CEM containing information on multiple inputs for one program, using nodes
or paths from the Base CEMs, like inputs can be
grouped together and unlike inputs can be distinguished from each other.

This section describes work to identify the input of a
program by using information in the Composite CEM. Statically identifying
inputs can be useful in categorizing the different inputs of a
program. The program behavior can depend on the input and it can be
useful to categorize these different behaviors according to the input.

Dynamically identifying inputs can also be useful. If a system is
running many different input sets for the same program, these methods
can be used to figure out which input is running. Using previously determined
characteristics about the input run, a run-time system could make more informed
decisions. For example, in a dual core environment if one program that uses memory
heavily is running, a run-time system would want to schedule a compute intensive
program with the memory intensive job to reduce resource contention and increase
throughput.

The following subsections describe and analyze both node and paths
methods for input identification.

%The previous section described a method for predicting execution within one
%running program. Before this can be done, the system must know what
%program is running. It may be the case that a system will run the same
%program but with different data sets and/or different input parameters. The
%composite CEM holds the ability to possibly distinguish between different runs
%of the same program.
%
%This section describes four approaches to input identification. These approach
%use analysis of the nodes and paths found during execution. Four key pieces of
%information that will be relevant for each of the approaches are:
%
%\begin{itemize}
%
%    \item \textit{Theoretical Limit} - The effectiveness of the identification
%will be heavily depended upon the composite CEM for that program. The more
%shared nodes there are in the CEM, the harder it will be to determine the actual
%input. (note later that this may not hurt because if all the input behave
%similarly we won't have to necessarily be correct) Analysis can be done to see
%the limit of effectiveness of the identification.
%
%    \item \textit{Time to Identification} - This is the time it takes to
%successfully identify the input. Time is given as the number of stages from the
%first attempt at identification to the sucessful identification.
%
%    \item \textit{Required Information} - This is the specific information
%needed about the CEM to perform the given approach. This will dictate the amount
%of memory needed for each approach.
%
%    \item \textit{Complexity of Lookup} - This will determine that given the
%approach and the required information, how complex is the calculation that
%determines whether the input can be identified.
%
%\end{itemize}
%
%Table~\ref{table:input_id} summarizes these points for each of the approaches.
%The approaches are described and analyzed in the following sections. The five
%SPEC2000 benchmarks that have three or more refrenece inputs - 164.gzip,
%176.gcc, 252.eon, 253.perlbmk and 256.bzip2 - are used to analyze each approach.
%
%\begin{table}[ht!]
%\vspace{0.1in}
%\center
%\begin{tabular}{|l|l|l|}
%\hline
%\multicolumn{3}{|c|}{Input Identification} \\
%\hline\hline
%\multirow{4}{*}{Node}
%    & Limit & Percentage of stages belonging to a unqiue node \\
%\cline{2-3}
%    & Time & Number of stages until a unique node is found \\
%\cline{2-3}
%    & Data & List of nodes for each input \\
%\cline{2-3}
%    & Complexity & One item lookup into each list \\
%\hline
%\multirow{4}{*}{Node Set}
%    & Limit & 1 if unique node set exists, 0 if not \\
%\cline{2-3}
%    & Time & Number of stages until a unique node set is found \\
%\cline{2-3}
%    & Data & List of nodes for each input \\
%\cline{2-3}
%    & Complexity & Node set lookup into each list \\
%\hline
%\multirow{4}{*}{Node}
%    & Limit & Percentage of unqiue paths in the timeline \\
%\cline{2-3}
%    & Time & Number of stages until a unique path is created \\
%\cline{2-3}
%    & Data & Timeline for each input \\
%\cline{2-3}
%    & Complexity & Path lookup into each timeline \\
%\hline
%\multirow{4}{*}{Node}
%    & Limit & 1 if unique set of paths exists, 0 if not \\
%\cline{2-3}
%    & Time & Number of stages until a unique set of paths is created \\
%\cline{2-3}
%    & Data & Timeline for each input \\
%\cline{2-3}
%    & Complexity & Path set lookup into each timeline \\
%\hline
%\end{tabular}
%\caption{Summary of identification methods.}
%\label{table:input_id}
%\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Identifying Input Execution Using Unique Nodes}~\label{sec:pred_input_id_node}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A very straight forward way of identifying an
input using a Composite CEM is to see if the current stage that is executing
exists in a unique node of the program's Composite CEM. If the stage belongs to a
node that is shared between two or more inputs then an identification
cannot be made.

%\begin{table}[t!]
%%\vspace{0.1in}
%\center
%\begin{tabular}{|l|l|l|l|l|l|l|}
%\hline
%\multicolumn{7}{|c|}{Unique Node Contribution}\\
%\hline\hline
%&&164.gzip&176.gcc&252.eon&253.perlbmk&256.bzip2\\
%\hline
%Total Nodes&&78&314&8&49&120\\
%\hline
%\multirow{2}{*}{ref.0}
%    &\# unique&1&10&0&6&12\\
%\cline{2-7}
%    &\% timeline&0.00&0.18&0.00&0.05&0.30\\
%\hline
%\multirow{2}{*}{ref.1}
%    &\# unique&3&48&0&0&3\\
%\cline{2-7}
%    &\% timeline&1.04&1.39&0.00&0.00&0.24\\
%\hline
%\multirow{2}{*}{ref.2}
%    &\# unique&0&4&1&1&14\\
%\cline{2-7}
%    &\% timeline&0.00&0.21&0.00&36.62&0.80\\
%\hline
%\multirow{2}{*}{ref.3}
%    &\# unique&5&1&&0&\\
%\cline{2-7}
%    &\% timeline&3.46&0.01&&0.00&\\
%\hline
%\multirow{2}{*}{ref.4}
%    &\# unique&14&16&&0&\\
%\cline{2-7}
%    &\% timeline&2.13&0.47&&0.00&\\
%\hline
%\multirow{2}{*}{ref.5}
%    &\# unique&&&&0&\\
%\cline{2-7}
%    &\% timeline&&&&0&\\
%\hline
%\multirow{2}{*}{ref.6}
%    &\# unique&&&&2.00&\\
%\cline{2-7}
%    &\% timeline&&&&0.01&\\
%\hline
%\end{tabular}
%\caption{Using unique node information to identify inputs.}
%\label{table:input_id_node}
%\end{table}

To test the effectiveness of the unique node method of input
identification, program timelines are
parsed to see if the input can be identified
and many stages it takes to identify the input. To attempt
identifying inputs of a program, the timeline for each of the inputs of the
SPEC2000 programs with more than 3 inputs (164.gzip, 176.gcc, 252.eon,
253.perlbmk and 256.bzip2) are taken and a stage
in that timeline is selected as the starting point. The
stages would be visited until a stage is found that belonged to a
unique node. The number of stages to get to this node is recorded to
signify the time taken to do the identification. For the experiment,
20 evenly distributed stages are selected as starting points. The
results of the experiment can be seen in
Table~\ref{table:input_id_node_results}.

\begin{table}[t!]
%\vspace{0.1in}
\center
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{5}{|c|}{Unique Node Method Results}\\
\hline
Program&Input&Min Stages&Max Stages&Avg Stages\\
\hline\hline
\multirow{5}{*}{164.gzip}
    &ref.0&3117&28448&13937\\
%\cline{2-6}
    &ref.1&3&21450&7610\\
%\cline{2-6}
    &ref.2&&&\\
%\cline{2-6}
    &ref.3&1&2965&564\\
%\cline{2-6}
    &ref.4&2&18252&4036\\
\hline\hline
\multirow{5}{*}{176.gcc}
    &ref.0&165&8478&3146\\
%\cline{2-6}
    &ref.1&2&5663&891\\
%\cline{2-6}
    &ref.2&106&3378&1209\\
%\cline{2-6}
    &ref.3*(19)&66&6111&3088\\
%\cline{2-6}
    &ref.4&10&3202&725\\
\hline\hline
\multirow{3}{*}{252.eon}
    &ref.0&&&\\
%\cline{2-6}
    &ref.1&&&\\
%\cline{2-6}
    &ref.2&4309&86418&45363\\
\hline\hline
\multirow{7}{*}{253.perlbmk}
    &ref.0*(14)&667&20175&9746\\
%\cline{2-6}
    &ref.1&&&\\
%\cline{2-6}
    &ref.2&1&13646&4672\\
%\cline{2-6}
    &ref.3&&&\\
%\cline{2-6}
    &ref.4&&&\\
%\cline{2-6}
    &ref.5&&&\\
%\cline{2-6}
    &ref.6&2090&70083&28985\\
\hline\hline
\multirow{3}{*}{256.bzip2}
    &ref.0&42&919&304\\
%\cline{2-6}
    &ref.1&78&40374&9006\\
%\cline{2-6}
    &ref.2&4&619&252\\
\hline
\end{tabular}
\caption{Input identification results for 5 SPEC2000 benchmarks for 20 starting
points over the input timeline using the unique node method.}
\label{table:input_id_node_results}
\end{table}

A vast majority of the inputs are identified from all 20 starting
points. Those denoted with an "*" are successful in less than 20 of
the starting points while those rows that are left blank represent
inputs that could not be identified.

One input from 164.gzip, two inputs from 252.eon and four inputs from
253.perlbmk are unable to be identified. The inability to identify these inputs
corresponds to the 0\%
of unique nodes in these inputs. Most of
the rest of the inputs showed a good ability to be identified but at
the cost of varying numbers of stages.

Figure~\ref{fig:input_id_node_176_gcc} shows the results for the
inputs of 176.gcc over the entire timeline. This graph reports the
number of stages to the identification for each of the starting
points. Starting point one is the first stage of the timeline with
starting point 2 being 5\% into the timeline and finally starting
point 20 is 95\% into the timeline.

In Figure~\ref{fig:input_id_node_176_gcc} the lines with a constant negative
slope show starting points that are chasing the same unique node meaning that
there is a large portion of the timeline that is made up of shared nodes.

\begin{figure}[t!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.5]{fig/176_gcc_input_id_node.pdf} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Identifying inputs in 176.gcc using unique nodes.}
\label{fig:input_id_node_176_gcc}
\end{figure}

The unique node approach to input identification showed some good
results. Many of the inputs are identified though sometimes at the
cost of looking at many stages. There are two advantages to the unique node
search approach. First, little memory is needed to store the required
information. Only
a list of nodes for each of the inputs is needed. Second, the algorithm for
identifying the input is simple and fast. The algorithm consists of a lookup using the
current node into the node list for each input.
Though the unique node search method has these advantages, the results can be
improved by adding to the method.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Identifying Input Execution Using Unique Node Sets}~\label{sec:pred_input_id_node_set}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Aside from single unique nodes, an input can be characterized by a unique set of
nodes. What the unique node approach lacks is the knowledge of where the
program has executed in the past. If the history of executed nodes is recorded, the
identification of the input can be done by seeing if the set of executed nodes
is unique to that input. This method requires the same information as the unique
node approach but the algorithm to perform the identification is slightly more complex as
a set of nodes must now be compared against each input's list of nodes.

To see how beneficial this increased cost is, the experiment
previously described is run again with the node set being
tracked as the stages in the timeline are visited. The results of
this experiment are shown in
Table~\ref{table:input_id_nodeset_results}.

\begin{table}[h!]
%\vspace{0.1in}
\center
%\begin{tabular}{|l|l|l|l|l|l|l|}
\begin{tabular}{|p{1.0in}|p{0.75in}|p{0.5in}|p{0.5in}|p{0.5in}|p{0.5in}|p{0.5in}|}
\hline
\multicolumn{7}{|c|}{Unique Node Set Method Results}\\
\hline
Program&Input&Min Stages&Max Stages&Avg Stages&Avg Set Size&Window Unique Sets\\
\hline\hline
\multirow{5}{*}{164.gzip}
    &ref.0&8&3741&1042&10&63.20\\
%\cline{2-8}
    &ref.1&3&21450&7610&14&45.10\\
%\cline{2-8}
    &ref.2&9&2946&530&9&80.53\\
%\cline{2-8}
    &ref.3&1&2386&271&4&75.06\\
%\cline{2-8}
    &ref.4&2&2833&870&10&62.47\\
\hline\hline
\multirow{5}{*}{176.gcc}
    &ref.0&165&8478&3146&39&47.20\\
%\cline{2-8}
    &ref.1&2&5662&849&32&77.12\\
%\cline{2-8}
    &ref.2&106&2924&898&27&61.15\\
%\cline{2-8}
    &ref.3&66&4432&1668&22&42.76\\
%\cline{2-8}
    &ref.4&10&3202&697&28&73.12\\
\hline\hline
\multirow{3}{*}{252.eon}
    &ref.0&&&&&\\
%\cline{2-8}
    &ref.1&&&&&\\
%\cline{2-8}
    &ref.2&4309&86418&45363&4&0.03\\
\hline\hline
\multirow{7}{*}{253.perlbmk}
    &ref.0*(14)&667&20175&6822&4&29.55\\
%\cline{2-8}
    &ref.1&&&&&\\
%\cline{2-8}
    &ref.2&1&13646&4672&4&46.76\\
%\cline{2-8}
    &ref.3*(19)&6120&103720&52174&23&8.40\\
%\cline{2-8}
    &ref.4&&&&&\\
%\cline{2-8}
    &ref.5*(12)&3365&27817&9257&14&20.96\\
%\cline{2-8}
    &ref.6&2090&27439&13121&21&48.45\\
\hline\hline
\multirow{3}{*}{256.bzip2}
    &ref.0&37&645&202&13&65.26\\
%\cline{2-8}
    &ref.1&78&3680&679&20&61.00\\
%\cline{2-8}
    &ref.2&4&417&207&14&68.90\\
\hline
\end{tabular}
\caption{Input identification results for 5 SPEC2000 benchmarks for 20 starting
points over the input timeline using the unique node set method.}
\label{table:input_id_nodeset_results}
\end{table}

The results show that overall the unique node set method is more
successful in identifying inputs and the method took fewer
stages to get an identification compared to the unique node method.
In the worst case the unique node set
had the same maximum stages to identification.
Since any time a unique node is found a unique node set will result,
the worst case for the unique node set method is the number of stages taken by
the unique node method. The unique node set approach is still unsuccessful in
identifying two inputs from 252.eon and two inputs from 253.perlbmk.

Table~\ref{table:input_id_nodeset_results} also reports the average
number of nodes in the unique node set that identified the input. After the
inputs are identified, the average set size is used as a window size to slide
across the timeline.
Starting at the beginning of the timeline the window is used to create a set of nodes.
This set is then used to lookup to see if it is a unique set. The window is
then advanced by one stage and the same action is performed. The percentage of
windows resulting in unique node sets is reported in the last column.
Comparing the unique node sets to individual unique nodes, the unique node sets
provide more program coverage than individual unique nodes.

Figure~\ref{fig:input_id_nodeset_176_gcc} shows the unique node set
results over the starting points for 176.gcc. The graph in
Figure~\ref{fig:input_id_nodeset_176_gcc} is similar to the graph in
Figure~\ref{fig:input_id_node_176_gcc}. Some starting points result in faster
identifications for the unique node set method, but as mentioned earlier, the
worst case is the result from the unique node method. The increase in lookup
complexity results in improved identification in some cases but the improvements
are not overwhelming.

\begin{figure}[h!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.43]{fig/176_gcc_input_id_nodeset.pdf} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Identifying inputs in 176.gcc using unique node sets.}
\label{fig:input_id_nodeset_176_gcc}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection{Issues with Node Methods}~\label{sec:pred_input_id_node_issues}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%This method is limited by the number of unique nodes in a
%given input.  The more occurrences of unique nodes, the better the
%chance to identify an input.  Table~\ref{table:input_id_node} shows
%the number of unique nodes for the different inputs of the SPEC2000
%benchmarks 164.gzip, 176.gcc, 252.eon, 253.perlbmk and 256.bzip2.  The
%table also shows the percentage of the timeline that is made up of
%these unique nodes. Most SPEC2000 programs have small
%percentages of unique nodes with the exception of 253.perlbmk.

\begin{figure}[h!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.43]{fig/spec2000_shared_unq_dist} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Distribution of shared and unique nodes in program timelines for 5
of the SPEC2000 benchmarks.}
\label{fig:shared_unq_node_dist}
\end{figure}

The main limitation of the node methods is the number of unique nodes found
across inputs of a program. Looking at Figure~\ref{fig:2000_composite_nodes} all
but one program have at least 75\% of the nodes as shared nodes.
Figure~\ref{fig:shared_unq_node_dist} shows the distribution of shared and
unique nodes in these same programs.
The graph in Figure~\ref{fig:shared_unq_node_dist} shows that for all programs
except 175.vpr and one input run of 253.perlbmk, almost all of the execution is
made up of shared nodes leaving little opportunity for the unique node method
and a small opportunity for the unique node set method.

Looking closer at the unique nodes in the runs that do have them,
Figure~\ref{fig:2000_unique_contrib} shows the contribution of the unique nodes
to the portion of the program that is made up of unique nodes. The graph shows a
range of results from only a few nodes that make up the unique execution to
those that have many different unique nodes in the unique execution.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.5]{fig/spec2000_unique_contrib} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Contribution of unique nodes in SPEC2000 integer benchmarks.}
\label{fig:2000_unique_contrib}
\end{figure}

In some cases it may not be important to distinguish the input as input may
behave the same. On the other hand, there may be programs that vary with inputs
so it would be important to distinguish. For the latter case, methods other than
nodes methods may be required.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Identifying Input Execution Using Unique Paths}~\label{sec:pred_input_id_path}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

As described in Chapter~\ref{chap:methodology} another way to look at
a program is through the paths that are found in its
timeline. Like the unique node method, the unique path approach
identifies the input by keeping track of the current path of
some specified length. The path is searched among the
timelines of each input to find matches.  If the path exists in only
one input, then the input is correctly identified.

The unique path method is limited by the existence of unique paths in an input.
Table~\ref{table:input_id_path} shows the total paths, the unique
paths and the program coverage from those unique paths.
A path length of 5 is used for the analysis to maintain a low lookup time for
the identification.
The program coverage from the unique paths varies much like the
coverages from the node sets shown in
Table~\ref{table:input_id_nodeset_results}. The number of unique paths
also varies widely. The first two inputs of 253.perlbmk have only five
unique paths but they account for a large portion of the
program. Looking at 164.gzip, there are many unique paths which end up
accounting for a large percentage of the program.


\begin{table}[t!]
%\vspace{0.1in}
\center
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{5}{|c|}{Program Unique Paths}\\
\hline
    Program&Input&Total Paths&Unq Paths&Program Coverage\\
\hline\hline
\multirow{5}{*}{164.gzip}
    &ref.0&71935&1397&5.99\\
%\cline{2-3}
    &ref.1&32814&1288&9.33\\
%\cline{2-3}
    &ref.2&72981&4628&71.38\\
%\cline{2-3}
    &ref.3&59291&699&75.64\\
%\cline{2-3}
    &ref.4&150469&17018&16.84\\
\hline\hline
\multirow{5}{*}{176.gcc}
    &ref.0&20778&1313&17.70\\
%\cline{2-3}
    &ref.1&66952&11435&27.05\\
%\cline{2-3}
    &ref.2&6539&884&14.68\\
%\cline{2-3}
    &ref.3&6713&349&7.43\\
%\cline{2-3}
    &ref.4&36239&7001&22.97\\
\hline\hline
\multirow{3}{*}{252.eon}
    &ref.0&67793&4&0.01\\
%\cline{2-3}
    &ref.1&48633&3&0.01\\
%\cline{2-3}
    &ref.2&86427&5&0.01\\
\hline\hline
\multirow{7}{*}{253.perlbmk}
    &ref.0&32430&128&3.28\\
%\cline{2-3}
    &ref.1&1240&5&99.76\\
%\cline{2-3}
    &ref.2&21524&5&36.62\\
%\cline{2-3}
    &ref.3&108441&2633&4.33\\
%\cline{2-3}
    &ref.4&56708&980&2.03\\
%\cline{2-3}
    &ref.5&53409&1067&2.50\\
%\cline{2-3}
    &ref.6&94025&1586&2.21\\
\hline\hline
\multirow{3}{*}{256.bzip2}
    &ref.0&85705&12906&36.53\\
%\cline{2-3}
    &ref.1&116283&10781&32.50\\
%\cline{2-3}
    &ref.2&102824&11020&16.63\\
\hline
\end{tabular}
\caption{Unique paths of length 5 from SPEC2000 benchmarks with 3 or more
reference inputs.}
\label{table:input_id_path}
\end{table}

To compare the unique path method to the node methods, the same experiment
is run.  The same 20 starting points from the timelines are used and
the stages are counted until a unique path is found. The results
from the experiment are shown in Table~\ref{table:input_id_path_results}.

\begin{table}[t!]
%\vspace{0.1in}
\center
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{5}{|c|}{Unique Path Method Results}\\
\hline
Program&Input&Min Stages&Max Stages&Avg Stages\\
\hline\hline
\multirow{5}{*}{164.gzip}
    &ref.0&5&1555&218\\
%\cline{2-6}
    &ref.1&5&882&183\\
%\cline{2-6}
    &ref.2&5&2240&119\\
%\cline{2-6}
    &ref.3&5&10&5\\
%\cline{2-6}
    &ref.4&5&300&65\\
\hline\hline
\multirow{5}{*}{176.gcc}
    &ref.0&5&588&126\\
%\cline{2-6}
    &ref.1&5&193&31\\
%\cline{2-6}
    &ref.2&5&527&98\\
%\cline{2-6}
    &ref.3&5&738&148\\
%\cline{2-6}
    &ref.4&5&474&68\\
\hline\hline
\multirow{3}{*}{252.eon}
    &ref.0&3330&67737&35533\\
%\cline{2-6}
    &ref.1*(1)&8&8&8\\
%\cline{2-6}
    &ref.2&4309&86418&45363\\
\hline\hline
\multirow{7}{*}{253.perlbmk}
    &ref.0&10&8715&1464\\
%\cline{2-6}
    &ref.1&5&8&5\\
%\cline{2-6}
    &ref.2&5&13646&4673\\
%\cline{2-6}
    &ref.3&9&6569&494\\
%\cline{2-6}
    &ref.4&5&3502&375\\
%\cline{2-6}
    &ref.5&22&3557&473\\
%\cline{2-6}
    &ref.6&11&5333&464\\
\hline\hline
\multirow{3}{*}{256.bzip2}
    &ref.0&5&134&39\\
%\cline{2-6}
    &ref.1&5&399&61\\
%\cline{2-6}
    &ref.2&5&332&132\\
\hline
\end{tabular}
\caption{Input identification results for 5 SPEC2000 benchmarks for 20 starting
points over the input timeline using the unique path method.}
\label{table:input_id_path_results}
\end{table}

A noticeable difference in the path results are that all inputs are
successfully identified. The first input of 252.eon is only identified once
but the rest of the inputs are identified from all 20 starting
points. Comparing the results to the unique node set method, the
maximum stages to identification are very similar; however, the average number
of states is lower using the unique path method.

Figure~\ref{fig:input_id_path_176_gcc} shows the results over the 20
staring points in the timeline for 176.gcc. Since the maximum stages to
identification for 176.gcc are much less in the unique path method,
the y-axis scale is much smaller than that of the graphs for the two
node methods. There are fewer long straight lines in this case
meaning that many of the starting points are able to find a unique
path before the occurrence of the next starting point. On average, the unique
path method requires fewer stages to identify inputs as compared to
the node methods.

\begin{figure}[t!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.5]{fig/176_gcc_input_id_path.pdf} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Identifying inputs in 176.gcc using unique paths.}
\label{fig:input_id_path_176_gcc}
\end{figure}

With the average case being the best using the unique path approach it
may seem that it would be the best candidate for use. The downside to
the unique path approach is that the amount if information that is
needed is larger than the node methods and the lookup into the
information may be much longer. A path must be run through the
timelines to see if there is a match. In the static case this may not
be a concern but for use in a dynamic environment, memory size and
complexity are factors in selecting an approach.

A possible solution to reducing the required information and the lookup
complexity is to only store the unique paths for each input instead of the
entire timeline. Ideally, there would be few unique paths in each input that
could be used to identify that input.
Figure~\ref{fig:path_5_unq_contrib} shows the contribution from a
certain percentage of the top unique paths in the program. As the
percentage of unique paths (the x-axis) approaches 100\%, the coverage
reported in Table~\ref{table:input_id_path} is reached.

\begin{figure}[t!]
    \centering
    \begin{tabular}{cc}
        \centering
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.25]{fig/164_gzip_unq_path_contrib}
        \hspace{2pt}
        \end{minipage} &
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.25]{fig/176_gcc_unq_path_contrib}
        \end{minipage}
        \\  (a) \textit{164.gzip.} &
            (b) \textit{176.gcc.}
    \end{tabular} 
    \begin{tabular}{cc}
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.25]{fig/253_perlbmk_unq_path_contrib} 
        \hspace{2pt} 
        \end{minipage} &
        \begin{minipage}{0.5\textwidth}         \centering
        \includegraphics[scale=0.25]{fig/256_bzip2_unq_path_contrib}
        \end{minipage}
        \\  (c) \textit{253.perlbmk.} &
            (d) \textit{256.bzip2.} 
    \end{tabular} 
    \caption{Contribution of unique 5 stage paths for 4 SPEC2000 benchmarks.}
    \label{fig:path_5_unq_contrib}
\end{figure}

Since in most cases the program's timelines are not made up of a large
percentage of unique paths, all of the unique paths would have to be stored to
effectively identify the inputs. Since the number of paths is large, it may be
more feasible to store the timelines and perform a search using the generated
path.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Identification of Nodes Using Program Counter Profiles}~\label{sec:pred_pc_node}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Since the nodes in the CEM are created based on basic block execution
frequency, it is interesting to note how the basic blocks are
distributed among the nodes. The top 25\% of nodes are taken in each
program for one reference input. The first PC for the top executing
basic blocks are recorded. Next, the lists from the nodes are
compared to see how many times each basic block
appeared. Figure~\ref{fig:node_pc_dist} shows the results from two
SPEC2000 benchmarks using a slice size of 10M instructions.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.35]{fig/176_gcc_pc_dist} \\
            \hspace{10pt}(a) \textit{176.gcc.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.35]{fig/197_parser_pc_dist} \\
            \hspace{10pt}(b)\textit{197.parser.}
        \end{minipage} \\
    \end{tabular}
    \caption{Distribution of PCs in program nodes for 176.gcc and 197.parser.}
\label{fig:node_pc_dist}
\end{figure}

The graphs shown in Figure~\ref{fig:node_pc_dist} represent the PC
values on the x-axis and the number of nodes each PC is found in on
the y-axis. In Figure~\ref{fig:node_pc_dist}(a) 176.gcc shows that a
majority of the top PCs are found in only one node. In contrast,
Figure~\ref{fig:node_pc_dist} shows that the top PCs in 197.parser are
more distributed among the top nodes.

Figure~\ref{fig:node_pc_dist} shows that there are programs
where the current node
may be predictable from sampling the PC of the basic block but there
are others where this may not be the case. For the SPEC2000 integer
benchmarks, the results varied evenly between results shown for
176.gcc and results shown for 197.parser.

Since the CEMs are built from code points it is interesting to see that
197.parser has top executing PC values that span many of the top nodes.
197.parser has one of the more complex CEMs in terms of the number of nodes and
transitions meaning that 197.parser does not have a regular pattern to its
execution which causes the PC values to be spread among the program nodes. On
the other hand, 164.gzip has a regular pattern to its execution as it repeatedly
compresses and uncompresses the input file. Figure~\ref{fig:node_pc_dist}(a)
shows that about 60\% of the PCs are found in one node and over 90\% of the top
PCs are found in no more than two nodes making predicting the current node from
a PC value much easier in a program like 164.gzip as opposed to a program like
197.parser.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Applications of Prediction and Identification}~\label{sec:pred_applications}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Using the CEM, this chapter has shown different predictions and
identifications that can be performed. These techniques have
programs in several areas of computer systems.
First, the identification techniques are useful in static program and
system design analysis. The CEM serves as a characterization of any
workload and can show how that workload executed in a particular
system. This information can be useful in making decisions in both
system design and programming.

The prediction techniques have programs in both operating systems
and run-time systems. Armed with the ability to create, store and
lookup CEMs, an OS or run-time system can make decisions based on
run-time events.

If a system can detect what program is running and knows its prior
behavior, the system can be intelligent in the way it schedules it
with other programs.  For example, by not running two memory
intensive programs together, the system can achieve a higher
throughput. This idea can be extended to any measurable metric such as
power, temperature or possibly fault tolerance.

All of the
aforementioned techniques rely on the ability to determine what node
is currently executing. For prediction, the system must first know
where the program is executing before it can predict where the
program will be executing in the future. For identification, the
system must properly identify the nodes.

An experiment is presented
that attempts to identify the currently executing node by sampling the
basic block vectors that are executing. The easy solution is to track every
basic block as the PinPoints profiling tool does as it will always
result in the proper node, but profiling every basic block may introduce
too much overhead for a real
system. For this reason, a sampling technique is used to attempt to
identify the currently executing node. Using the Pin~\cite{pin-web} binary
instrumentation tool, pintools~\cite{pintool} can be written to profile
programs. The PinPoints pintool using in collecting the BBVs is extended to turn
sampling on and off according to the sampling size.

\begin{figure}[b!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.5]{fig/node_prediction_2000int} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Run-time CP-BBV creation using basic block sampling for a single
reference input of the SPEC2000 integer benchmarks.}
\label{fig:node_prediction}
\end{figure}

As mentioned in Chapter~\ref{chap:methodology}, a pivot clustering
algorithm is used as it is a viable algorithm for use in a run-time
system. For the experiment samples are taken from each
program slice and using these samples, the CP-BBV is created as
described in Section~\ref{sec:meth_exe-create}. The CP-BBV is then
compared to the known vectors for the program nodes to see how close the sample
CP-BBV is to the actual CP-BBV. When the correct vector is found, the
identification is recored as correct. The graph in
Figure~\ref{fig:node_prediction} shows the results for the SPEC2000
integer benchmarks with the sample size on the x-axis and the accuracy on the
y-axis.

The curves of Figure~\ref{fig:node_prediction} fall into four categories. The
first category consists of the five programs that show above 75\% accuracy no
matter what the sampling size is. Four program fall into the second category of
slightly improving accuracy as the sample size increases. The third category
consists of the one program which drastically improves as the the sample size
increases. Finally, 197.parser is in its own category as it never reaches 40\%
accuracy meaning that the behavior of 197.parser cannot be captured by low
sample techniques.

An implementation in a real system may benefit from hardware
assistance.  Dedicated hardware could perform the basic block sampling
and clustering while the operating system or run-time system could use
this information. The work in~\cite{hw_prof-1} describes using hardware for
optimization. Similar steps could be taken to have hardware for collecting CEM
information. Shadow Profiling~\cite{shadow-prof} is another technique that could
be used to gather and process basic block information. The Shadow Profiling work
leverages other cores on a system to profile a program running on another core.
This approach reduces overhead on the running program while still being able to
profile the program.
